142. Linked List Cycle II

Solution 1: HashSet

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return None
        
        nodeSet = set()
        ptrA = head
        while ptrA:
            if ptrA in nodeSet:
                return ptrA
            nodeSet.add(ptrA)
            ptrA = ptrA.next
        
        return None

Time Complexity: O(N)
Space Complexity: O(N)

Solution 2: Floyd's Cycle Algorithm

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or head.next is None:
            return None
        
        ptrSlow = head
        ptrFast = head
        # Detect cycle
        while ptrFast and ptrFast.next:
            ptrSlow = ptrSlow.next
            ptrFast = ptrFast.next.next
            if ptrSlow == ptrFast:
                break
        if ptrFast is None or ptrFast.next is None:
            return None
        
        # Check the intersection
        ptrSlow = head
        while ptrSlow != ptrFast:
            ptrSlow = ptrSlow.next
            ptrFast = ptrFast.next

        return ptrSlow

Time Complexity: O(N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/linked-list-cycle-ii/discuss/1701055/JavaC%2B%2BPython-best-explanation-ever-happen's-for-this-problem
https://matthung0807.blogspot.com/2020/04/floyd-cycle-detection-algorithm-floyd.html
https://ithelp.ithome.com.tw/articles/10223721